#include "main/utils.h"
using namespace std;


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      int len = nums.size();
      vector<int> pre_max(len), back_max(len);
      for (int i = 0; i < len; ++i) {
        if (i % k == 0) {
          pre_max[i] = nums[i];
        } else {
          pre_max[i] = max(pre_max[i - 1], nums[i]);
        }
      }

      for (int i = len - 1; i >= 0; --i) {
        if (i == len - 1 || (i + 1) % k == 0) {
          back_max[i] = nums[i];
        } else {
          back_max[i] = max(back_max[i + 1], nums[i]);
        }
      }
      vector<int> ans;
      for (int i = 0; i <= len - k; ++i) {
        ans.push_back(max(back_max[i], pre_max[i + k - 1]));
      }
      return ans;
    }

    vector<int> maxSlidingWindow1(vector<int>& nums, int k) {
      int len = nums.size();
      priority_queue<pair<int, int>> pri_que;
      for (int i = 0; i < k; ++i) {
        pri_que.emplace(nums[i], i);
      }
      vector<int> ans;
      ans.push_back(pri_que.top().first);
      for (int i = k; i < len; ++i) {
        pri_que.emplace(nums[i], i);
        while (pri_que.top().second <= (i - k)) {
          pri_que.pop();
        }
        ans.push_back(pri_que.top().first);
      }
      return ans;
    }

    vector<int> maxSlidingWindow2(vector<int>& nums, int k) {
      int len = nums.size();
      deque<int> que;
      for (int i = 0; i < k; ++i) {
        while (!que.empty() && nums[i] >= nums[que.back()]) {
          que.pop_back();
        }
        que.push_back(i);
      }

      vector<int> ans;
      ans.push_back(nums[que.front()]);
      for (int i = k; i < len; ++i) {
        while (!que.empty() && nums[i] >= nums[que.back()]) {
          que.pop_back();
        }
        que.push_back(i);
        while (que.front() <= (i - k)) {
          que.pop_front();
        }
        ans.push_back(nums[que.front()]);
      }
      return ans;
    }
};

int main() {
  vector<int> input = {1, 3, -1, -3, 5, 3, 6, 7};
  int k = 3;
  Solution su;
  auto output = su.maxSlidingWindow(input, k);
  printVec("output", output);
  auto output1 = su.maxSlidingWindow1(input, k);
  printVec("output1", output1);
  auto output2 = su.maxSlidingWindow2(input, k);
  printVec("output2", output2);
}
